package com.sakura.二分查找;

import java.util.Arrays;

// 给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
//
//同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
//
//请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。
// https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/description/
public class Code01_咒语和药水的成功对数 {

    public static void main(String[] args) {
        int[] spells = {5,1,3};
        int[] potions = {1,2,3,4,5};
        long success = 7;
        System.out.println(successfulPairs(spells, potions, success));
    }

    public static int[] successfulPairs(int[] spells, int[] potions, long success) {
        // 排序
        Arrays.sort(potions);
        int n = potions.length;
        int[] ans = new int[spells.length];
        int i = 0;
        for (int spell : spells) {
            ans[i++] = n - lowerBound(potions, spell, success);
        }
        return ans;
    }

    // 返回找到的，最大超过success的下标
    public static int lowerBound(int[] nums, long spell, long target) {
        int left = -1, right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] * spell >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
